package com.lw.leetcode.arr.b;

/**
 * create by idea
 * arr
 * 1914. 循环轮转矩阵
 *
 * @author lmx
 * @version 1.0
 * @date 2021/11/28 20:21
 */
public class RotateGrid {

    public static void main(String[] args) {
        RotateGrid test = new RotateGrid();

//        int[][] grid = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}, {17,18,19,20}, {21,22,23,24}};
//        int k = 1;

        int k = 25;
        int[][] grid = {
                {3970,1906,3608,298,3072,3546,1502,773,4388,3115,747,3937},
                {2822,304,4179,1780,1709,1058,3645,681,2910,2513,4357,1038},
                {4471,2443,218,550,2766,4780,1997,1672,4095,161,4645,3838},
                {2035,2350,3653,4127,3208,4717,4347,3452,1601,3725,3060,2270},
                {188,2278,81,3454,3204,1897,2862,4381,3704,2587,743,3832},
                {996,4499,66,2742,1761,1189,608,509,2344,3271,3076,108},
                {3274,2042,2157,3226,2938,3766,2610,4510,219,1276,3712,4143},
                {744,234,2159,4478,4161,4549,4214,4272,701,4376,3110,4896},
                {4431,1011,757,2690,83,3546,946,1122,2216,3944,2715,2842},
                {898,4087,703,4153,3297,2968,3268,4717,1922,2527,3139,1516},
                {1086,1090,302,1273,2292,234,3268,2284,4203,3838,2227,3651},
                {2055,4406,2278,3351,3217,2506,4525,233,3829,63,4470,3170},
                {3797,3276,1755,1727,1131,4108,3633,1835,1345,1293,2778,2805},
                {1215,84,282,2721,2360,2321,1435,2617,1202,2876,3420,3034}};
        int[][] ints = test.rotateGrid(grid, k);
    }

    public int[][] rotateGrid(int[][] grid, int k) {
        int a = grid.length;
        int b = grid[0].length;
        int a1 = a >> 1;
        int b1 = b >> 1;
        int m = Math.min(a1, b1);
        for (int i = 0; i < m; i++) {
            int len = (a + b - (i << 2) - 2) << 1;
            int k1  = k %  len;
            if (k1 == 0) {
                continue;
            }
            int[] arr2 = new int[len];
            int xend = b - 1 - i;
            int yend = a - 1 - i;
            int index = 0;
            for (int j = i; j < xend; j++) {
                arr2[index++] = grid[i][j];
            }
            for (int j = i; j < yend; j++) {
                arr2[index++] = grid[j][xend];
            }
            for (int j = xend; j > i; j--) {
                arr2[index++] = grid[yend][j ];
            }
            for (int j = yend; j > i; j--) {
                arr2[index++] = grid[j ][i];
            }
            find(arr2, 0, len - 1);
            find(arr2, 0, len - 1 - k1);
            find(arr2, len - k1, len - 1);
            index = 0;
            for (int j = i; j < xend; j++) {
                 grid[i][j] = arr2[index++];
            }
            for (int j = i; j < yend; j++) {
              grid[j][xend] = arr2[index++];
            }
            for (int j = xend; j > i; j--) {
               grid[yend][j ] = arr2[index++];
            }
            for (int j = yend; j > i; j--) {
               grid[j ][i] = arr2[index++];
            }
        }
        return grid;
    }

    private void find (int[] arr, int st, int end) {
        int item;
        while (st < end) {
            item = arr[st];
            arr[st++] = arr[end];
            arr[end--] = item;
        }
    }

}
